<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>thread</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="thread">thread</h1>
<h1 id="1-leetcode-1114-print-in-order">1. leetcode 1114. Print in Order</h1>
<ul>
<li><a href="https://leetcode.com/problems/print-in-order/">https://leetcode.com/problems/print-in-order/</a></li>
</ul>
<p>suppose we have a class:</p>
<pre><code class="language-java"><div><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Foo</span> </span>{
  <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">first</span><span class="hljs-params">()</span> </span>{ print(<span class="hljs-string">"first"</span>); }
  <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">second</span><span class="hljs-params">()</span> </span>{ print(<span class="hljs-string">"second"</span>); }
  <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">third</span><span class="hljs-params">()</span> </span>{ print(<span class="hljs-string">"third"</span>); }
}
</div></code></pre>
<p>The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().</p>
<h2 id="5-python-threading-solutions-barrier-lock-event-semaphore-condition-with-explanation">5 Python threading solutions (Barrier, Lock, Event, Semaphore, Condition) with explanation</h2>
<h3 id="raise-two-barriers">Raise two barriers.</h3>
<p>Both wait for two threads to reach them.</p>
<p>First thread can print before reaching the first barrier. Second thread can print before reaching the second barrier. Third thread can print after the second barrier.</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> threading <span class="hljs-keyword">import</span> Barrier

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Foo</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.first_barrier = Barrier(<span class="hljs-number">2</span>)
        self.second_barrier = Barrier(<span class="hljs-number">2</span>)
            
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">first</span><span class="hljs-params">(self, printFirst)</span>:</span>
        printFirst()
        self.first_barrier.wait()
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">second</span><span class="hljs-params">(self, printSecond)</span>:</span>
        self.first_barrier.wait()
        printSecond()
        self.second_barrier.wait()
            
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">third</span><span class="hljs-params">(self, printThird)</span>:</span>
        self.second_barrier.wait()
        printThird()
</div></code></pre>
<h3 id="start-with-two-locked-locks">Start with two locked locks.</h3>
<p>First thread unlocks the first lock that the second thread is waiting on. Second thread unlocks the second lock that the third thread is waiting on.</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> threading <span class="hljs-keyword">import</span> Lock

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Foo</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.locks = (Lock(),Lock())
        self.locks[<span class="hljs-number">0</span>].acquire()
        self.locks[<span class="hljs-number">1</span>].acquire()
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">first</span><span class="hljs-params">(self, printFirst)</span>:</span>
        printFirst()
        self.locks[<span class="hljs-number">0</span>].release()
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">second</span><span class="hljs-params">(self, printSecond)</span>:</span>
        <span class="hljs-keyword">with</span> self.locks[<span class="hljs-number">0</span>]:
            printSecond()
            self.locks[<span class="hljs-number">1</span>].release()
            
            
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">third</span><span class="hljs-params">(self, printThird)</span>:</span>
        <span class="hljs-keyword">with</span> self.locks[<span class="hljs-number">1</span>]:
            printThird()
</div></code></pre>
<h3 id="events">events</h3>
<p>Set events from first and second threads when they are done. Have the second thread wait for first one to set its event. Have the third thread wait on the second thread to raise its event.</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> threading <span class="hljs-keyword">import</span> Event

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Foo</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.done = (Event(),Event())
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">first</span><span class="hljs-params">(self, printFirst)</span>:</span>
        printFirst()
        self.done[<span class="hljs-number">0</span>].set()
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">second</span><span class="hljs-params">(self, printSecond)</span>:</span>
        self.done[<span class="hljs-number">0</span>].wait()
        printSecond()
        self.done[<span class="hljs-number">1</span>].set()
            
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">third</span><span class="hljs-params">(self, printThird)</span>:</span>
        self.done[<span class="hljs-number">1</span>].wait()
        printThird()
</div></code></pre>
<h3 id="semaphor">Semaphor</h3>
<p>Start with two closed gates represented by 0-value semaphores. Second and third thread are waiting behind these gates. When the first thread prints, it opens the gate for the second thread. When the second thread prints, it opens the gate for the third thread.</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> threading <span class="hljs-keyword">import</span> Semaphore

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Foo</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.gates = (Semaphore(<span class="hljs-number">0</span>),Semaphore(<span class="hljs-number">0</span>))
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">first</span><span class="hljs-params">(self, printFirst)</span>:</span>
        printFirst()
        self.gates[<span class="hljs-number">0</span>].release()
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">second</span><span class="hljs-params">(self, printSecond)</span>:</span>
        <span class="hljs-keyword">with</span> self.gates[<span class="hljs-number">0</span>]:
            printSecond()
            self.gates[<span class="hljs-number">1</span>].release()
            
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">third</span><span class="hljs-params">(self, printThird)</span>:</span>
        <span class="hljs-keyword">with</span> self.gates[<span class="hljs-number">1</span>]:
            printThird()
</div></code></pre>
<h3 id="conditions">conditions</h3>
<p>Have all three threads attempt to acquire an RLock via Condition. The first thread can always acquire a lock, while the other two have to wait for the order to be set to the right value. First thread sets the order after printing which signals for the second thread to run. Second thread does the same for the third.</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> threading <span class="hljs-keyword">import</span> Condition

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Foo</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.exec_condition = Condition()
        self.order = <span class="hljs-number">0</span>
        self.first_finish = <span class="hljs-keyword">lambda</span>: self.order == <span class="hljs-number">1</span>
        self.second_finish = <span class="hljs-keyword">lambda</span>: self.order == <span class="hljs-number">2</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">first</span><span class="hljs-params">(self, printFirst)</span>:</span>
        <span class="hljs-keyword">with</span> self.exec_condition:
            printFirst()
            self.order = <span class="hljs-number">1</span>
            self.exec_condition.notify(<span class="hljs-number">2</span>)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">second</span><span class="hljs-params">(self, printSecond)</span>:</span>
        <span class="hljs-keyword">with</span> self.exec_condition:
            self.exec_condition.wait_for(self.first_finish)
            printSecond()
            self.order = <span class="hljs-number">2</span>
            self.exec_condition.notify()

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">third</span><span class="hljs-params">(self, printThird)</span>:</span>
        <span class="hljs-keyword">with</span> self.exec_condition:
            self.exec_condition.wait_for(self.second_finish)
            printThird()
</div></code></pre>
<h1 id="2-leetcode-1115-print-foobar-alternately">2. leetcode 1115. Print FooBar Alternately</h1>
<ul>
<li><a href="https://leetcode.com/problems/print-foobar-alternately/">https://leetcode.com/problems/print-foobar-alternately/</a></li>
</ul>
<p>Suppose you are given the following code:</p>
<pre><code class="language-java"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">FooBar</span> </span>{
  <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">foo</span><span class="hljs-params">()</span> </span>{
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++) {
      print(<span class="hljs-string">"foo"</span>);
    }
  }

  <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">bar</span><span class="hljs-params">()</span> </span>{
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++) {
      print(<span class="hljs-string">"bar"</span>);
    }
  }
}
</div></code></pre>
<p>The same instance of FooBar will be passed to two different threads. Thread A will call foo() while thread B will call bar(). Modify the given program to output &quot;foobar&quot; n times.</p>
<p>答案是</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> threading <span class="hljs-keyword">import</span> Semaphore

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">FooBar</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, n)</span>:</span>
        self.n = n
        self.s1 = Semaphore(<span class="hljs-number">1</span>)
        self.s2 = Semaphore(<span class="hljs-number">0</span>)


    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">foo</span><span class="hljs-params">(self, printFoo: <span class="hljs-string">'Callable[[], None]'</span>)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(self.n):
            self.s1.acquire()
            <span class="hljs-comment"># printFoo() outputs "foo". Do not change or remove this line.</span>
            printFoo()
            self.s2.release()

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">bar</span><span class="hljs-params">(self, printBar: <span class="hljs-string">'Callable[[], None]'</span>)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(self.n):
            self.s2.acquire()
            <span class="hljs-comment"># printBar() outputs "bar". Do not change or remove this line.</span>
            printBar()
            self.s1.release()
            
</div></code></pre>
<h1 id="3-leetcode-1116">3. leetcode 1116.</h1>
<p>最开始我的答案是下面这样，会死锁</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> threading <span class="hljs-keyword">import</span> Semaphore

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ZeroEvenOdd</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, n)</span>:</span>
        self.n = n
        self.c = <span class="hljs-number">0</span>
        self.s0 = Semaphore(<span class="hljs-number">1</span>)
        self.s1 = Semaphore(<span class="hljs-number">0</span>)
        self.s2 = Semaphore(<span class="hljs-number">0</span>)

        
	<span class="hljs-comment"># printNumber(x) outputs "x", where x is an integer.</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">zero</span><span class="hljs-params">(self, printNumber: <span class="hljs-string">'Callable[[int], None]'</span>)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        <span class="hljs-keyword">while</span> self.c &lt; self.n:
            self.s0.acquire()
            printNumber(<span class="hljs-number">0</span>)
            self.c += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> self.c % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
                self.s1.release()
            <span class="hljs-keyword">else</span>:
                self.s2.release()
            
        
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">even</span><span class="hljs-params">(self, printNumber: <span class="hljs-string">'Callable[[int], None]'</span>)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        <span class="hljs-keyword">while</span> self.c &lt; self.n:
            self.s1.acquire()
            printNumber(self.c)
            self.s0.release()
        
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">odd</span><span class="hljs-params">(self, printNumber: <span class="hljs-string">'Callable[[int], None]'</span>)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        <span class="hljs-keyword">while</span> self.c &lt; self.n:
            self.s2.acquire()
            printNumber(self.c)
            self.s0.release()
        
        
</div></code></pre>
<p>正确的答案是</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> threading <span class="hljs-keyword">import</span> Semaphore

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ZeroEvenOdd</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, n)</span>:</span>
        self.n = n
        self.c = <span class="hljs-number">0</span>
        self.s0 = Semaphore(<span class="hljs-number">1</span>)
        self.s1 = Semaphore(<span class="hljs-number">0</span>)
        self.s2 = Semaphore(<span class="hljs-number">0</span>)

        
	<span class="hljs-comment"># printNumber(x) outputs "x", where x is an integer.</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">zero</span><span class="hljs-params">(self, printNumber: <span class="hljs-string">'Callable[[int], None]'</span>)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(self.n):
            self.s0.acquire()
            printNumber(<span class="hljs-number">0</span>)
            self.c += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> self.c % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
                self.s1.release()
            <span class="hljs-keyword">else</span>:
                self.s2.release()
            
        
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">even</span><span class="hljs-params">(self, printNumber: <span class="hljs-string">'Callable[[int], None]'</span>)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(self.n//<span class="hljs-number">2</span>):
            self.s1.acquire()
            printNumber(self.c)
            self.s0.release()
        
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">odd</span><span class="hljs-params">(self, printNumber: <span class="hljs-string">'Callable[[int], None]'</span>)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range((self.n+<span class="hljs-number">1</span>)//<span class="hljs-number">2</span>):
            self.s2.acquire()
            printNumber(self.c)
            self.s0.release()    

</div></code></pre>

    </body>
    </html>